package com.bm;

import com.future.util.ListNode;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * Description: BM55 没有重复项数字的全排列
 *
 * @author weiruibai.vendor
 * Date: 2022/9/19 09:29
 */
public class BM55 {

    public static void main(String[] args) {
        BM55 bm55 = new BM55();
        int[] nums = new int[]{1, 2, 3};
        System.out.println(bm55.permute(nums));

    }

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (num.length == 1) {
            ans.add(new ArrayList<Integer>() {{
                add(num[0]);
            }});

            return ans;
        }
        process(ans, num, new ArrayList<Integer>(), new HashSet<Integer>());
        return ans;
    }

    private void process(ArrayList<ArrayList<Integer>> ans, int[] num,
                         ArrayList<Integer> tmpAns, HashSet<Integer> repeat) {
        if (repeat.size() == num.length) {
            ans.add(new ArrayList<>(tmpAns));
            return;
        }
        for (int j = 0; j < num.length; j++) {
            if (repeat.add(num[j])) {
                tmpAns.add(num[j]);
                process(ans, num, tmpAns, repeat);
                tmpAns.remove(tmpAns.size() - 1);
                repeat.remove(num[j]);
            }
        }
    }

    /**
     * Description:
     *
     * @author weiruibai.vendor
     * Date: 2022/3/5 01:31
     */
    public static class BM4 {
    }

    /**
     * Description:
     *
     * @author weiruibai.vendor
     * Date: 2022/3/5 09:51
     */
    public static class M3_reverseKGroup {

        public static void main(String[] args) {
            ListNode head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(3);
            head.next.next.next = new ListNode(4);
            head.next.next.next.next = new ListNode(5);
            int k = 5;
            ListNode listNode = reverseKGroup(head, k);
            print(listNode);
        }


        public static ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || k == 1) {
                return head;
            }
            ListNode ans = new ListNode(-1);
            ListNode op = head;
            while (op != null) {
                head = op;
                int curIndex = 1;
                while (curIndex < k && op.next != null) {
                    op = op.next;
                    curIndex++;
                }
                if (curIndex == k) {
                    ListNode next = op.next;
                    op.next = null;
                    // 反转
                    ListNode newReverse = reverse(head);
                    ListNode lastNode = getLastNode(ans);
                    lastNode.next = newReverse;
                    op = next;
                }else {
                    ListNode lastNode = getLastNode(ans);
                    lastNode.next = head;
                    break;
                }
            }

            return ans.next;
        }

        private static ListNode getLastNode(ListNode head) {
            if (head == null) {
                return null;
            }
            while (head.next != null) {
                head = head.next;
            }
            return head;
        }

        private static void print(ListNode head) {
            while (head != null) {
                System.out.print(head.val + " ");
                head = head.next;
            }
        }

        private static ListNode reverse(ListNode head) {
            ListNode pre = null;
            while (head != null) {
                ListNode next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
    }

    /**
     * Description:
     *
     * @author weiruibai.vendor
     * Date: 2022/3/5 10:58
     */
    public static class mergeKLists_BM5 {

        public static void main(String[] args) {

            ListNode head = new ListNode(2);
            /*head.next = new ListNode(3);
            head.next.next = new ListNode(6);*/

            ListNode head2 = new ListNode(-1);
            /*head2.next = new ListNode(4);*/


            ListNode head3 = new ListNode(10);
            head3.next = new ListNode(19);

            ListNode head4 = new ListNode(100);
            head4.next = new ListNode(190);

            // {-7,-7,-6,-4,-4,1,1},{-10,-9,-8,-7,-7,-5,-2,2},{-10,3},{},{},{-5,-4,-4,-4,-1,-1,4},{},{-10,-5,-3,-1,1,2},{-10,-9,-5,-4,-3,-1,-1}

            ArrayList<ListNode> list = new ArrayList<ListNode>() {{
                add(head);
                add(head2);
                //add(head3);
                //add(head4);
                //add(null);
                add(new ListNode());
            }};
            ListNode listNode = mergeKLists(list);
            print(listNode);
        }


        public static ListNode mergeKLists(ArrayList<ListNode> lists) {
            if (lists == null || lists.size() == 0) {
                return null;
            } else if (lists.size() == 1) {
                return lists.get(0);
            }
            ListNode ans = new ListNode(Integer.MIN_VALUE);
            ListNode curNode = ans;
            int k = lists.size();
            while (k > 0) {
                int curIndex = 0;
                ListNode firstNode = lists.get(0);
                if (firstNode == null) {
                    lists.remove(0);
                    k = lists.size();
                    continue;
                }
                for (int j = 1; j < k; j++) {
                    ListNode next = lists.get(j);
                    if (next == null) {
                        lists.remove(j);
                        k = lists.size();
                        continue;
                    }
                    if (firstNode.val > next.val) {
                        firstNode = lists.get(j);
                        curIndex = j;
                    }
                }
                curNode.next = firstNode;
                curNode = curNode.next;
                if (firstNode.next == null) {
                    lists.remove(curIndex);
                } else {
                    lists.remove(curIndex);
                    lists.add(curIndex, firstNode.next);
                }
                k = lists.size();
            }

            return ans.next;
        }


        private static void print(ListNode head) {
            while (head != null) {
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
    }

    /**
     * Description:
     *
     * @author weiruibai.vendor
     * Date: 2022/3/5 00:22
     */
    public static class reverseBetween_BM2 {

        public static void main(String[] args) {
            ListNode head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(3);
            head.next.next.next = new ListNode(4);
            head.next.next.next.next = new ListNode(5);
            int m = 3, n = 4;
            reverseBetween(head, m, n);

        }

        public static ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null || m == n) {
                return head;
            }
            ListNode op = new ListNode(-1);
            op.next = head;
            ListNode dump = op;
            int curIndex = 1;
            while (op != null && curIndex < m) {
                op = op.next;
                curIndex++;
            }
            ListNode first = dump;
            ListNode middle = op.next;
            op.next = null;
            op = middle;
            while (op != null && curIndex < n) {
                op = op.next;
                curIndex++;
            }
            ListNode tail = op.next;
            op.next = null;
            ListNode ans = first;
            while (first.next != null) {
                first = first.next;
            }
            middle = reverse(middle);
            first.next = middle;
            while (middle.next != null) {
                middle = middle.next;
            }
            middle.next = tail;
            ans = ans.next;
            print(ans);
            return ans;
        }

        private static ListNode reverse(ListNode head) {

            ListNode pre = null;
            while (head != null) {
                ListNode next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }

        private static void print(ListNode head) {
            while (head != null) {
                System.out.print(head.val + " ");
                head = head.next;
            }
        }
    }
}
